#include <bits/stdc++.h>

int main() {
  freopen("oi.in", "r", stdin);
  freopen("oi.out", "w", stdout);
  freopen("oi.err", "w", stderr);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int cid, test;
  std::cin >> cid >> test;
  while (test--) {
    int N, M;
    std::cin >> N >> M;
    std::vector<int> ex(M), ey(M);
    for (int i = 0; i < M; i++) { std::cin >> ex[i] >> ey[i]; }
    if (3 <= cid && cid <= 4) {
      std::cout << -2 * (N - 1) << ' ' << 114514 << '\n'; 
      continue;
    }
    std::vector<std::pair<int, int>> edges;
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        edges.emplace_back(i, j);
      }
    }
    int G = (int) edges.size(), mx = INT_MIN, cnt = 0;
    for (int st = 0; st < (1 << G); st++) {
      if (__builtin_popcount(st) != M - 1) { continue; }
      std::vector<std::vector<int>> dist(N, std::vector<int>(N, 1E7));
      for (int i = 0; i < N; i++) { dist[i][i] = 0; }
      for (int i = 0; i < G; i++) {
        if (st >> i & 1) {
          int u, v;
          std::tie(u, v) = edges[i];
          dist[u][v] = dist[v][u] = 1;
        }
      }
      for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
          for (int j = 0; j < N; j++) {
            dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
          }
        }
      }
      int cost = 0;
      for (int i = 0; i < M; i++) { cost -= dist[ex[i] - 1][ey[i] - 1]; }
      if (cost > mx) { mx = cost, cnt = 0; }
      if (cost == mx) { cnt++; }
    }
    std::cout << mx << ' ' << cnt << '\n';
  }

  return 0;
}